--[[
    链表：
    单向链表
    头结点.next->尾结点.next->null
    双向链表
    prev.头结点.next
    --------
    {prev, data, next}
    循环链表
        单向
            尾结点.next -> 头结点

        双向
            尾结点.next -> 头结点
            头结点.prev -> 尾结点

    local node = {
        next = nil,
        prev = nil,
        data = {}, --存放的逻辑数据对象
        id = 0, --用于比较大小
    }
--]]

local table_insert = table.insert
local table_remove = table.remove



local Link = {}

function Link.new(...)
    local instance = setmetatable({}, {__index=Link})
    instance:ctor(...)
    return instance
end

--[[
    ltype 1:单向 2:双向 3：循环单向 4：循环双向
--]]
function Link:ctor(ltype)
    if not ltype then
        ltype = 1
    end
    self.ltype = ltype
    self.head = nil
    self.tail = nil
end

function Link:add(node)
    if not self.head then
        self.head = node
        self.tail = node
        return
    end
    if self.ltype == 1 then
        self.tail.next = node
        self.tail = node
        return
    end
    if self.ltype == 2 then
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
        return
    end
    if self.ltype == 3 then
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
        self.tail.next = self.head
        return
    end
    if self.ltype == 4 then
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
        self.tail.next = self.head
        self.head.prev = self.tail
        return
    end
end

function Link:delete(node)
    if not self.head or not self.tail then
        return
    end
    local pre_node = nil
    local cur_node = self.head

    if self.ltype == 1 then
        while cur_node do
            if cur_node.id == node.id then
                if not pre_node then
                    --删除的是头节点
                    self.head = cur_node.next
                    break
                end
                pre_node.next = cur_node.next
                break
            end
            pre_node = cur_node
            cur_node = cur_node.next
        end
        return true
    end
    if self.ltype == 2 then
        while cur_node do
            if cur_node.id == node.id then
                if not pre_node then
                    --删除的是头节点
                    self.head = cur_node.next
                    break
                end
                pre_node.next = cur_node.next
                cur_node.prev = pre_node
                break
            end
            pre_node = cur_node
            cur_node = cur_node.next
        end
        return true
    end
    if self.ltype == 3 then
        while cur_node do
            if cur_node.id == node.id then
                if not pre_node then
                    --删除的是头节点
                    self.head = cur_node.next
                    self.tail.next = self.head
                    break
                end
                pre_node.next = cur_node.next
                break
            end
            pre_node = cur_node
            cur_node = cur_node.next
        end
        return true
    end
    if self.ltype == 4 then
        while cur_node do
            if cur_node.id == node.id then
                if not pre_node then
                    --删除的是头节点
                    self.head = cur_node.next
                    self.tail.next = self.head
                    break
                end
                pre_node.next = cur_node.next
                cur_node.prev = pre_node
                break
            end
            pre_node = cur_node
            cur_node = cur_node.next
        end
        return true
    end
end

function Link:print()
    if self.ltype == 1 or self.ltype == 2 then
        local node = self.head
        while node do
            print(node.id)
            node = node.next
        end
        return
    end
    if self.ltype == 3 or self.ltype == 4 then
        local node = self.head
        while node do
            print(node.id)
            node = node.next
            if node.id == self.head.id then
                break
            end
        end
        return
    end

end



------------------------------------------------------------------
--测试
------------------------------------------------------------------
if arg and arg[0] == "link.lua" then

    --单向
    print("_____1111111__")
    local list = Link.new()
    list:add({id=1,})
    list:add({id=5,})
    list:add({id=8,})
    list:add({id=4,})
    list:add({id=2,})
    list:print()
    print("_______")
    local a = list:delete({id=3})
    local a = list:delete({id=1})
    list:add({id=15,})
    print("delete:", a)
    print("_______")
    list:sort()
    list:print()

    --双向
    print("_____222222222222222222222222__")
    local Link = Link.new(2)
    Link:add({id=1,})
    Link:add({id=2,})
    Link:print()

    --循环单向
    print("_____3333333333333333__")
    local Link = Link.new(3)
    Link:add({id=1,})
    Link:add({id=2,})
    Link:print()

    print("_____4444444444444444__")

    --循环双向
    local link = Link.new(4)
    link:add({id=1,})
    link:add({id=2,})
    print("head:",link.tail.next.id)
    link:delete({id=1})
    link:print()

end

return Link